package com.dhnsoft.代码随想录.字符串;

/**
 * ClassName: d07_459_重复的子字符串
 * Package: com.dhnsoft.代码随想录.字符串
 * Description:
 *
 * @Author dhn
 * @Create 2024/3/19 10:30
 * @Version 1.0
 */
public class d07_459_重复的子字符串 {

    public static void main(String[] args) {
        boolean abab = repeatedSubstringPattern("ababa");
        System.out.println(abab);
    }

    public static boolean repeatedSubstringPattern(String s) {
        if(s==null){
            return false;
        }
        char[] chars = s.toCharArray();
        int len = chars.length;
        int j = 0;
        int[] next = new int[len];
        next[0] = 0;
        for (int i=1;i<len;i++){
            while (j>0&&chars[j]!=chars[i])
                j = next[j-1];
            if(chars[j]==chars[i])
                j++;
            next[i] = j;
        }
        if(next[len-1]>0&&(len%(len-next[len-1])==0)){
            return true;
        }
        return false;
    }
}
